#include "Traversal.h"
//二叉树节点的赋值
BinaryTree* BinaryTreeCreate(int x)
{
    BinaryTree *newnode = (BinaryTree*)malloc(sizeof (BinaryTree));
    if(newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    newnode->val = x;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}
//二叉树前序遍历--根左右
void PreOrderTraversal(BinaryTree* root)
{
    if(root == NULL)
        return;
    printf("%d ",root->val);
    PreOrderTraversal(root->left);
    PreOrderTraversal(root->right);
}
//二叉树中序遍历--左根右
void InOrderTraversal(BinaryTree* root)
{
    if(root == NULL)
        return;
    InOrderTraversal(root->left);
    printf("%d ",root->val);
    InOrderTraversal(root->right);
}
//二叉树后序遍历--左右根
void PostOrderTraversal(BinaryTree* root)
{
    if(root == NULL)
        return;
    PostOrderTraversal(root->left);
    PostOrderTraversal(root->right);
    printf("%d ",root->val);
}
//求二叉树的节点个数
int BinaryTreeSize(BinaryTree* root)
{
    if(root == NULL)
        return 0;
    else
        return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
//求叶子节点的个数
int TreeLeafsSize(BinaryTree* root)
{
    if(root == NULL)
        return 0;
    if(root->left == NULL && root->right == NULL)
        return 1;
    return TreeLeafsSize(root->left) + TreeLeafsSize(root->right);
}
//求第k层节点个数
int TreeKSize(BinaryTree* root,int k)
{
    assert(k > 0);
    if(root == NULL)
        return 0;
    if(k == 1)
        return 1;
    return TreeKSize(root->left,k-1) + TreeKSize(root->right,k-1);
}
//求二叉树的深度
int Max(int x,int y)
{
    return x>y ? x : y;
}
int TreeHigh(BinaryTree* root)
{
    if(root == NULL)
        return 0;
    return Max(TreeHigh(root->left)+1, TreeHigh(root->right)+1);
}

//查找值为x的节点
BinaryTree * BinaryTreeFind(BinaryTree * root, int x)
{
    if(root == NULL)
        return NULL;
    if(root->val == x)
        return root;

    BinaryTree * find_left = BinaryTreeFind(root->left,x);
    if(find_left)
        return find_left;

    BinaryTree * find_right = BinaryTreeFind(root->right,x);
    if(find_right)
        return find_right;

    return NULL;
}